1. Field
This invention relates to the field of encryption and, more particularly, to a method useful in securely computing on encrypted data.
In one embodiment, the present invention relates to a method to securely compare two ciphertexts, which are each respective encryptions of two possibly different symbols, to form, without the use of secret keys or decryption, a ciphertext containing an encrypted indication of whether the symbols are the same.
2. Description of Related Art
Homomorphic encryption is a form of encryption which enables the performing of an operation on a pair of ciphertexts, producing a result which when decrypted is the same as if a corresponding operation had been performed on the plaintexts. The ciphertext operations for performing homomorphic multiplication and addition are referred to herein as EvalMult and EvalAdd, respectively. Throughout this disclosure the EvalAdd and EvalMult operations are understood to be modulus-2 operations, i.e., they are modulus-2 homomorphic addition and modulus-2 homomorphic multiplication, respectively.
For example, denoting the encryption and decryption operation as Enc and Dec respectively, we have for plaintexts a1 and a2, Dec(EvalMult(Enc(a1), Enc(a2)))=a1*a2, i.e., encrypting each of a1 and a2, operating on the resulting ciphertexts with the EvalMult operation, and decrypting the result, yields the product of a1 and a2, where modulus-2 arithmetic is implied throughout.
Similarly, the EvalAdd operation in a homomorphic encryption scheme has the property that for plaintexts a1 and a2, Dec(EvalAdd(Enc(a1), Enc(a2)))=a1+a2, i.e., encrypting each of a1 and a2, operating on the resulting cyphertexts with the EvalAdd operation and decrypting the result yields the sum of a1 and a2, where again modulus-2 arithmetic is implied throughout.
A homomorphic encryption scheme is referred to herein as somewhat homomorphic if its homomorphic characteristics support only a finite number of sequential EvalAdd or EvalMult operations. The number of EvalMult operations that may be performed on ciphertexts while ensuring that the result, when decrypted, will equal the product of the corresponding plaintexts is referred to herein as the multiplicative degree, or the depth, of the encryption scheme. An additive degree may be defined in an analogous manner. A somewhat homomorphic encryption scheme may have infinite additive degree but finite multiplicative degree. A homomorphic encryption scheme which has infinite additive degree and infinite multiplicative degree is referred to herein as a fully homomorphic encryption scheme.
An encryption scheme may be referred to as partially homomorphic if it supports only an EvalAdd or an EvalMult operation, but not both.
Homomorphic encryption may be useful, for example if an untrusted party is charged with processing data without having access to the data. A trusted party or data proprietor may encrypt the data, deliver it to the untrusted party, the untrusted party may process the encrypted data and return it to the data proprietor or turn it over to another trusted party. The recipient may then decrypt the results to extract the decrypted, processed data.
The operations desired may include comparison of symbols. An untrusted party may, for example, receive ciphertexts corresponding to two plaintext symbols from one or more data proprietors, and may wish to send a third party an encrypted indication of whether the plaintext symbols are the same, which the third party may decrypt, obtaining for example a binary 1 if the symbols match, i.e., are identical, and a binary 0 if they do not match. Thus, there is a need for a method for secure symbol comparison.